Sejarah lebuh raya ini bermula sejak pemisahan Singapura dari Malaysia, yang mengakibatkan kerajaan menjadikan Port Swettenham (kini Pelabuhan Klang) sebagai pelabuhan utama negara menggantikan Pelabuhan Singapura. Sehubungan itu, kerajaan merancang untuk membina sebuah lebuh raya bagi menghubungkan Pelabuhan Klang ke Kuala Lumpur dengan menaik taraf jajaran Jalan Kuala Lumpur-Klang sedia ada kepada sebuah lebuh raya penuh melalui penggantian persimpangan lampu isyarat searas kepada persimpangan bertingkat, menjadikan Lebuhraya Persekutuan sebagai lebuh raya ekspres pertama di Malaysia[1]. Dibina melalui pembiayaan daripada Bank Dunia, kerja naik taraf dimulakan dari tahun 1974 sehingga tahun 1977[1]. Lebuhraya Persekutuan pada asalnya ialah lebuh raya 4 lorong kecuali di bahagian Petaling Jaya di mana lebuh raya ini menjadi 6 lorong, tetapi pada tahun 1992 Plus Expressway Berhad, pemegang konsesi Lebuhraya Utara Selatan telah menaik taraf keseluruhan lebuh raya ini kepada 6 lorong.